import java.util.Stack;

public class Leetcode {
}

//leetcode:394:字符串解码
class Solution1 {
    public String decodeString(String s) {
        //创建一个数字栈
        Stack<Integer> stackint = new Stack<>();
        //创建一个字符串栈
        Stack<StringBuffer> stackString = new Stack<>();
        //在字符串栈中存入一个空串
        stackString.push(new StringBuffer());
        char[] ch = s.toCharArray();
        int n = ch.length;
        int i = 0;
        //遍历数组
        while(i < n) {
            //如果字符的值为数字
            if(ch[i] >= '0' && ch[i] <= '9') {
                //将数字整合在一起放入栈中
                int tmp = 0;
                while(i < n && ch[i] >= '0' && ch[i] <= '9') {
                    tmp = tmp * 10 + (ch[i] -'0');
                    i++;
                }
                stackint.push(tmp);
            }
            //如果是左'['
            else if(ch[i] == '[') {
                i++;//往下走
                //如果是字符将字符整合在一起，放入栈中
                StringBuffer tmp1 = new StringBuffer();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z') {
                    tmp1.append(ch[i]);
                    i++;
                }
                stackString.push(tmp1);
            }
            //如果是右']'
            else if(ch[i] == ']') {
                //将数字栈和字符串栈的栈顶元素弹出
                int x = stackint.pop();
                StringBuffer str = stackString.pop();
                //数字为多少就将栈顶后边添加多少的字符串
                while( x != 0) {
                    stackString.peek().append(str);
                    x--;
                }
                i++;
            }
            //如果字符不在'[]'中就将他们整合在一起，然后放到栈顶元素的后面
            else {
                StringBuffer tmp2 = new StringBuffer();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z') {
                    tmp2.append(ch[i]);
                    i++;
                }
                stackString.peek().append(tmp2);
            }
        }
        //最后字符串栈的栈顶元素就是我们要得到的结果
        return stackString.pop().toString();
    }
}

//leetcode:946:验证栈序列
class Solution2 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while(!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}